﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace StringSearch
{
    class AhoCorasickMatcher : Matcher
    {
        private int MAX_SYMBOLS = 256;
        private int _i;
        private int[,] _targets;
        private int[] _fails;
        private bool[] _terminals;
        private Dictionary<int, int> _map;
//         private Dictionary<int, int> _founds;
// 
//         public Dictionary<int, int> Founds
//         {
//             get
//             {
//                 return this._founds;
//             }
//         }

        private AhoCorasickMatcher()
        {

        }
        public AhoCorasickMatcher(string[] _patterns)
        {
            int state = 0;
            for (int i = 0; i < _patterns.Length; i++) state += _patterns[i].Length;
            this._patterns = _patterns;
            this._targets = new int[state + 1, MAX_SYMBOLS];
            for (int i = 0; i < this._targets.GetLength(0); i++)
            {
                for (int j = 0; j < this._targets.GetLength(1); j++)
                {
                    this._targets[i, j] = -1;
                }
            }
            this._fails = new int[state + 1];
            for (int i = 0; i < this._fails.Length; i++) this._fails[i] = -1;
            this._terminals = new bool[state + 1];
            this._map = new Dictionary<int, int>();
            this._founds = new Dictionary<int, List<int>>();
            TrieLikeAutomaton();
            MakeFailureFunction();
        }

        public override void Search(string str)
        {
            int p = this._i;
            for (int i = 0; i < str.Length; i++)
            {
                p = this.NextState(p, Convert.ToInt16(str[i]));
				if (this._terminals[p] == true)
				{
					if (!this._founds.ContainsKey(this._map[p]))
					{
						this._founds.Add(this._map[p], new List<int>());
					}
					this._founds[this._map[p]].Add(i);
				}
            }
        }

        private int NextState(int p, int a)
        {
            while (p >= 0 && this._targets[p, a] < 0) p = this._fails[p];
            return (p >= 0) ? this._targets[p, a] : this._i;
        }

        private void TrieLikeAutomaton()
        {
            
            int p, q, k = 0;
            this._i = 0;
            this._terminals[this._i] = false;

            for (int i = 0; i < this._patterns.Length; i++)
            {
                p = this._i;
                for (int j = 0; j < this._patterns[i].Length; j++)
                {
                    q = this._targets[p, Convert.ToInt16(this._patterns[i][j])];
                    if (q < 0)
                    {
                        q = ++k;
                        this._terminals[q] = false;
                        this._targets[p, Convert.ToInt16(this._patterns[i][j])] = q;
                    }
                    p = q;
                }
                this._terminals[p] = true;
                this._map.Add(p, i);
            }
        }

        private void MakeFailureFunction()
        {
            Queue<int> theta = new Queue<int>();
            this._fails[this._i] = -1;
            theta.Enqueue(this._i);
            int p, q;
            while (theta.Count > 0)
            {
                p = theta.Dequeue();
                for (int i = 0; i < MAX_SYMBOLS; i++)
                {
                    if (this._targets[p, i] > 0)
                    {
                        q = this._targets[p, i];
                        this._fails[q] = this.NextState(this._fails[p], i);
                        if (this._terminals[this._fails[q]] == true)
                        {
                            this._terminals[q] = true;
                            this._map.Add(q,this._map[this._fails[q]]);
                        }
                        theta.Enqueue(q);
                    }
                }
            }
        }
    }
}
